package com.example.leetcode.DFS;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 题目描述
 * 给定一个无重复数字的整数数组，求其所有的排列方式。
 * 输入输出样例
 * 输入是一个一维整数数组，输出是一个二维数组，表示输入数组的所有排列方式。
 * Input: [1,2,3]
 * Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
 * 可以以任意顺序输出，只要包含了所有排列方式即可。
 *
 * @Description TODO
 * @date 2021/5/19 10:26
 * @Author liuzhihui
 * @Version 1.0
 */
public class Solution_4_46 {
    public static void main(String[] args) {

    }
    public static List<List<Integer>> permute(int[] nums) {
        // 结果集
        List<List<Integer>> list = new ArrayList<>();
        // 用于记录一种排列方式
        List<Integer> list1=new ArrayList<>();
        dfs(nums,list,list1);
        return list;
    }

    private static void dfs(int[] nums, List<List<Integer>> list, List<Integer> list1) {
        // 递归出口，当前的排列组合元素个数等于nums的元素个数
        if (nums.length == list1.size()){
            // 将当前排列组合添加到结果集中
            list.add(list1);
            return;
        }

        // 遍历nums
        for (int num : nums) {
            // 判断当前排列组合中是否包含当前元素
            if (list1.contains(num)){
                continue;
            }
            // 当前排列组合不包含当前元素，将当前元素添加到排列组合
            list1.add(num);
            // 寻找其他可以添加到排列组合的元素
            dfs(nums, list, list1);
            // 回溯,寻找别的排列组合
            list1.remove(list1.size() - 1);
        }

    }
}
